Programmable logic devices (PLDs) (e.g., field programmable gate arrays (FPGAs), complex programmable logic devices (CPLDs), field programmable systems on chips (FPSCs), or other types of programmable devices) may be configured to provide user-defined features. PLDs typically include various components, such as programmable logic blocks (PLBs), memory blocks, digital signal processing blocks, input/output blocks, and other components. PLD components may be interconnected by programmable routing resources (e.g., signal paths) of the PLD to implement a desired circuit design. PLDs typically have a limited supply of routing resources available to provide connections between components of the PLD. This differs from conventional application-specific integrated circuits (ASICs) in which typically any desired signal path may be custom-manufactured for a particular application.
Unfortunately, existing approaches to PLD connection routing often fail to provide such routings efficiently. In one approach, maze routing techniques may be used to route connections one at a time. However, maze routing techniques may fail to route all desired connections or may fail to meet the timing requirements of a particular design. In such cases, ripup and reroute operations are subsequently performed to remove routed connections and attempt to reroute them through alternative routing resources of the PLD. Such operations are inefficient, often result in degraded PLD performance, and significantly increase the time and processing resources needed to determine connection routings for the PLD.
In another approach, negotiation routing techniques may be used to route multiple connections using shared routing resources. Resource conflicts among commonly-routed connections are then resolved based on priorities associated with the connections. For example, negotiation routing techniques may be “connection-based” (e.g., where connections of different signals are routed one at a time), or “signal-based” (e.g., where signals are routed one at a time, with each signal having one or more associated connections that are routed before additional signals are routed). Unfortunately, negotiation routing techniques typically suffer the same drawbacks as conventional maze routing techniques, thus requiring similar remedial ripup and reroute operations.
Accordingly, there is a need for an improved approach to the routing of connections in PLDs.
Embodiments of the present invention and their advantages are best understood by referring to the detailed description that follows. It should be appreciated that like reference numerals are used to identify like elements illustrated in one or more of the figures.